Algorithms

An algorithm/programme is a sequence of instructions which takes an input and produces an output. One might think that they are the same as mathematical functions, but that is not the case. A function specify what one wants to achieve and an algorithm tells us how to achieve what we want. In a way, a function specifies a problem and an algorithm solves that problem.

#![allow(unused)]
fn main() {
fn add(x: str, y: str) -> str {
	let i = max(x.len(), y.len()) - 1; // Iterating starts from the last - 1 element because indexing starts at 0
	let j = min(x.len(), y.len());
	let carry: bit = 0;
	
	let result: str[i+1]; // The result has the same length as the longest input
	
	while i > j {
		result[i] = xor(carry, )
	}
	// TODO
}
}

However, not every function is computable because not every problem has a solution. In fact, here is a problem which cannot be solved by any algorithm.

This is called the Halting problem and describes the situation where we want to know if a given programme gets stuck in an infinite loop. Being able to solve this problem would be exceptionally useful because it would mean that we could also for example make the ultimate antivirus detector. Unfortunately, the Halting problem is uncomputable. It is not that we do not know how to solve it, it is just that the problem cannot be solved. There is no algorithm $\text{HALTS}$, and there never will be, which when given an arbitrary algorithm $A$ and input $x$ can decide if $A$ gets stuck when given $x$ as an input.

Running Time

Some algorithms are inherently faster than others. Moreover, algorithms take more time to run on longer inputs. The way we measure how long an algorithm takes to run on a particular input is called its time complexity.

Precisely what an atomic operation is differs from one computational model to another. Cryptography operates on the bit-level and so it is most useful to use Boolean circuits to model it. This means that cryptography uses the logical gates AND, OR, NOT and NAND. These operations take in two bits and output a single bit and we assume that our computer can only do these four operations - they are our atomic operations and have a running time equal to 1. Any other operations we might want to do will have to be defined using these four operations (which is very much possible, do not worry).

However, when actually analysing an algorithm's time complexity, one rarely stoops down to the level of Boolean gates. Instead the atomic operations are inferred from context and usually represent lines. Fear not, for these discrepancies are taken care of by big-O notation.

Analysing Time Complexity

Analysing precise time complexity turns out be a highly non-trivial task and we are also not really interested in precisely knowing how an algorithm's time complexity, but rather we simply want to know how this complexity changes as the input's length increases. For example, the difference between $T(n)=n^7$ and $T(n)=3n^3+n^2+3$ is much more significant than the difference between $T(n)=3n^3+n^2+3$ and $T(n)=3n^3$. Furthermore, we are usually interested in the running time of the worst-case scenario. This is where big-O notation comes in.

Since big-O notation describes bounds, it is very useful for our case of comparing time complexities. When we say that $T(n)=O(n^2)$, we are saying that the algorithm will complete in at most $c\times n^2$ steps for some constant $c$ and every input large input length $n$. The reason we compare running time for large values of $n$ is that if the input length is small, then it does not really matter if the algorithm runs in $O(n^2)$ or $O(n^3)$ time. However, as $n$ grows it becomes evident that an algorithm running in $O(n^3)$ is much slower than an algorithm which runs in $O(n^2)$.

These examples show that big-O notation only provides a relative idea of the performance of an algorithm in general as the input grows larger. For example, an algorithm that runs in $T(n)=100000000000000\cdot n$ time is "faster" than an algorithm that runs in $T(n)=n^2$ according to big-O notation because the first one is $O(n)$ and the second one is $O(n^2)$. But clearly, for most practical purposes, the second algorithm will be faster (if $n=1000$, then the second algorithm takes a million steps to complete while the first takes... well... calculate it if you can be bothered). Nevertheless, the constants which are concealed by big-O notation are rarely so big and therefore, we need not worry about such extreme cases in general.

Here is a graph which provides a general overview of how running times compare to one another:

Efficient and Inefficient Algorithms

The time complexity of an algorithm tells us how the algorithm's performance scales as the input length grows larger and larger. It would be useful if there was a way to classify algorithms by their time complexity in order to obtain some useful information about their performance.

Notice that this definition of "efficient" naturally includes algorithms whose time complexity is better than polynomial, for example algorithms with $T(n)=\sqrt{n}$. This is true due to the fact that $\sqrt{n}=O(n)$. Similarly an algorithm running in ${\log }_2(n)$ time is considered efficient because ${\log }_2(n)$ is upper bound by $n$, too.

An inefficient algorithm is then any algorithm that is not efficient.

Problem Classes